城市群数量

[编程题]城市群数量

热度指数：1523 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 个节点的邻接矩阵 m。节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。

矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。

请你找出共有多少个城市群。

数据范围： $1 \le n \le 200 \$ ，矩阵中只包含 $0 \$ 和 $1 \$

示例1

输入

[[1,1,0],[1,1,0],[0,0,1]]

输出

说明

1 2 相连，3 独立，因此是 3 个城市群。

示例2

输入

[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

输出

说明

1 ， 2相连 ；2 ，3相连，4独立，因此是 1,2,3 属于一个城市群，4属于一个城市群。

算法知识视频讲解

Python 3

Density666

# python3
# 并查集做法
# 总城市肯定是m
# 每有两个城市互相连接，数量就减1 

class Solution:
    def __init__(self):
        self.n = 210 
        self.father = [i for i in range(self.n)]
    def find(self, u):
        if u == self.father[u]:
            return u
        self.father[u] = self.find(self.father[u])
        return self.father[u]
    
    def same(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return True 
        return False 
    
    def join(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return 
        self.father[u] = v
        pass     
    def citys(self , m: List[List[int]]) -> int:
        # write code here
        cnt = len(m)
        for i in range(len(m)):
            for j in range(len(m[0])):
                if m[i][j] == 1:
                    if not self.same(i, j):
                        self.join(i, j)
                        cnt -= 1
                    else:
                        continue
        return cnt

发表于 2022-08-15 05:56:19 回复(0)